package leetcode.code0416;

public class Solution2 extends Solution416 {

	private int N;

	@Override
	public boolean canPartition(int[] nums) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		if ((sum & 1) == 1) { // 奇数不能对半分
			return false;
		}
		this.N = nums.length;
		sum >>= 1;// 目标是从数组中找到和的找一半
		Boolean[][] dp = new Boolean[N + 1][sum + 1];// 存储找过的
		return this.f(nums, dp, 0, sum);
	}

	/**
	 * 从index位到最后，是否有能组成left数的组合
	 *
	 * @param nums  原始数组
	 * @param dp    缓存
	 * @param index 起始位置 原始数组的
	 * @param left  剩余待找数字
	 * @return
	 */
	private boolean f(int[] nums, Boolean[][] dp, int index, int left) {
		if (index == N) {// 所有数字都找过了，至此left是否为0
			dp[index][left] = left == 0 ? true : false;
			return dp[index][left];
		}
		if (dp[index][left] != null) {// 找过的，直接返回
			return dp[index][left];
		}
		int sub = left - nums[index];
		if (sub == 0) {// 将index作为被选数字，如果恰巧使得剩余数字归零，成功
			dp[index][left] = true;
			return true;
		}
		if (sub > 0) {// 大于0才继续找
			if (this.f(nums, dp, index + 1, sub)) {
				dp[index][left] = true;
				return true;
			}
		}
		if (this.f(nums, dp, index + 1, left)) {// 这一位不选，之后看看有没有满足left的组合
			dp[index][left] = true;
			return true;
		}
		dp[index][left] = false;// 所有选择都失败了
		return false;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
	}

}
